package org.example;

import java.util.*;
import java.util.Arrays;

// 单调栈
public class MonotonicStack {
    static class DailyTemperatures {
        // 739. 每日温度
        // 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，
        // 下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

        // 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度O(n)

        // 单调栈的本质就是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需遍历一次。
        // 更直白来说，就是用一个栈来记录我们遍历过的元素

        // 使用单调栈的时候首先要明确如下几点：
        // 1. 单调栈里存放的元素是什么？单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
        // 2. 单调栈里元素的递增呢？还是递减呢？即如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小的元素，单调栈就是递减的。

        // 使用单调栈的主要三个判断条件：
        // 1. 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况；
        // 2. 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况；
        // 3. 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况。
        public int[] dailyTemperatures(int[] temperatures) {
            int lens = temperatures.length;
            int[] res = new int[lens];
            /*
             * 如果当前遍历的元素大于栈顶元素，表示栈顶元素的右边最大的元素就是当前遍历的元素，所以弹出栈顶元素，并记录，
             * 如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系。
             * 否则的话，就可以直接入栈
             * 注意：单调栈里加入的元素是下标。
             */
            Deque<Integer> stack = new LinkedList<>();
            stack.push(0);
            for (int i = 1; i < lens; i++) {
                if (temperatures[i] <= temperatures[stack.peek()]) {
                    stack.push(i);
                } else {
                    while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                        res[stack.peek()] = i - stack.peek();
                        stack.pop();
                    }
                    stack.push(i);
                }
            }
            return res;
        }
    }

    // 496. 下一个更大元素 I
    // 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
    // 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
    // nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
    //
    // 示例 1:
    // 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
    // 输出: [-1,3,-1]
    // 解释:
    // 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
    // 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
    // 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
    static class NextGreaterElementI {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Stack<Integer> temp = new Stack<>(); // temp存放的是nums2的下标
            int[] res = new int[nums1.length];
            java.util.Arrays.fill(res, -1);
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < nums1.length; i++) {
                hashMap.put(nums1[i], i);
            }
            temp.add(0);
            for (int i = 1; i < nums2.length; i++) {
                if (nums2[i] <= nums2[temp.peek()]) {
                    temp.add(i);
                } else {
                    while (!temp.isEmpty() && nums2[i] > nums2[temp.peek()]) {
                        if (hashMap.containsKey(nums2[temp.peek()])) {
                            Integer index = hashMap.get(nums2[temp.peek()]);
                            res[index] = nums2[i];
                        }
                        temp.pop();
                    }
                    temp.add(i);
                }
            }
            return res;
        }
    }

    // 503.下一个更大元素II
    // 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
    // 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。
    // 如果不存在，则输出 -1 。
    // 示例 1:
    // 输入: nums = [1,2,1]
    // 输出: [2,-1,2]
    // 解释: 第一个 1 的下一个更大的数是 2；
    // 数字 2 找不到下一个更大的数；
    // 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

    // 数组成环或者收尾相连的过程，实际就是用取模运算计算得出
    static class NextGreaterElementsII {
        public int[] nextGreaterElements(int[] nums) {
            // 边界处理
            if (nums == null || nums.length <= 1) {
                return new int[]{-1};
            }
            int size = nums.length;
            int[] result = new int[nums.length]; // 存放结果
            Arrays.fill(result, -1);
            Stack<Integer> stack = new Stack<>(); // 栈中存放的是nums中的元素下标
            for (int i = 0; i < 2 * size; i++) {
                while (!stack.isEmpty() && nums[i % size] > nums[stack.peek()]) {
                    result[stack.peek()] = nums[i % size]; // 更新result
                    stack.pop();// 弹出栈顶
                }
                stack.push(i % size);
            }
            return result;
        }
    }

    // 接雨水
    static class Trap {
        // 暴力解
        public int trap(int[] height) {
            int sum = 0;
            for (int i = 0; i < height.length; i++) {
                // 第一个柱子和最后一个柱子不接雨水
                if (i == 0 || i == height.length - 1) {
                    continue;
                }
                int rHeight = height[i]; // 记录右边柱子的最高高度
                int lHeight = height[i]; // 记录左边柱子的最高高度
                for (int r = i + 1; r < height.length; r++) {
                    if (height[r] > rHeight) {
                        rHeight = height[r];
                    }
                }
                for (int l = i - 1; l >= 0; l--) {
                    if (height[l] > lHeight) {
                        lHeight = height[l];
                    }
                }
                int h = Math.min(lHeight, rHeight) - height[i];
                if (h > 0) {
                    sum += h;
                }
            }
            return sum;
        }

        // 双指针
        public int trap1(int[] height) {
            int length = height.length;
            if (length <= 2) {
                return 0;
            }
            int[] maxLeft = new int[length];
            int[] maxRight = new int[length];

            // 记录每个柱子左边柱子的最大高度
            maxLeft[0] = height[0];
            for (int i = 1; i < length; i++) {
                maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
            }

            // 记录每个柱子右边最大高度
            maxRight[length - 1] = height[length - 1];
            for (int i = length - 2; i >= 0; i--) {
                maxRight[i] = Math.max(height[i], maxRight[i + 1]);
            }

            // 求和
            int sum = 0;
            for (int i = 0; i < length; i++) {
                int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
                if (count > 0) {
                    sum += count;
                }
            }
            return sum;
        }

        // 单调栈的处理方式
        public int trap2(int[] height) {
            int size = height.length;
            if (size <= 2) {
                return 0;
            }
            // 单调递增栈，从栈顶到栈底
            Deque<Integer> stack = new LinkedList<>(); // 这里使用Stack提交时，执行耗时18ms，使用Deque提交时，执行耗时7ms
            stack.push(0);
            int sum = 0;
            for (int index = 1; index < size; index++) {
                if (height[index] < height[stack.peek()]) {
                    stack.push(index);
                } else if (height[index] == height[stack.peek()]) {
                    // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
                    // 因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
                    stack.pop();
                    stack.push(index);
                } else {
                    // 如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了
                    while (!stack.isEmpty() && height[index] > height[stack.peek()]) {
                        // 取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]
                        int mid = stack.pop();
                        if (!stack.isEmpty()) {
                            // 长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，
                            // 此时的栈顶元素st.peek()，就是凹槽的左边位置，下标为st.peek()，对应的高度为height[st.peek()]
                            // height[index]表示当前位置，即右边最大值
                            // height[stack.peek()]表示左边最小值
                            // height[mid]表示原栈顶元素，因为已经弹出了，当前是被作为中间的位置

                            // 其实可以发现就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水的

                            // 雨水的高度是min(凹槽左边高度，凹槽右边高度)-凹槽底部高度，表示为：int h = min(height[stack.peek()], height[index]) - height[mid];
                            // 雨水的宽度是凹槽右边的下标 - 凹槽左边的下标 - 1，表示为：int w = index - stack.peek() - 1;

                            // 当前凹槽雨水的体积就是：h * w
                            int h = Math.min(height[index], height[stack.peek()]) - height[mid];
                            int w = index - stack.peek() - 1;
                            int hold = h * w;
                            if (hold > 0) {
                                sum += hold;
                            }
                        }
                    }
                    stack.push(index);
                }
            }
            return sum;
        }

        public static void main(String[] args) {
            int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
            new Trap().trap1(height);
        }
    }

    // 84.柱状图中最大的矩形
    // 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
    // 求在该柱状图中，能够勾勒出来的矩形的最大面积。
    // 输入：heights = [2,1,5,6,2,3]
    // 输出：10
    // 解释：最大的矩形为图中红色区域，面积为 10
    static class LargestRectangleArea {
        // 单调栈：本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
        // 栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
        // 如下三种情况：
        // 1. 情况一：当前遍历的元素heights[i]大于栈顶元素heights[stack.peek()]的情况；
        // 2. 情况二：当前遍历的元素heights[i]等于栈顶元素heights[stack.peek()]的情况；
        // 3. 情况三：当前遍历的元素heights[i]小于栈顶元素heights[stack.peek()]的情况。
        public int largestRectangleArea(int[] heights) {
            Deque<Integer> stack = new LinkedList<>();
            // 数组扩容，在头和尾各加入一个元素,为了解决[2,4,6,8]、[8,6,4,2]这种场景
            int[] newHeights = new int[heights.length + 2];
            newHeights[0] = 0;
            newHeights[newHeights.length - 1] = 0;
            for(int i = 0; i < heights.length; i++){
                newHeights[i + 1] = heights[i];
            }
            heights = newHeights;
            stack.push(0);
            int result = 0;
            // 第一个元素已经入栈，从下标1开始

            // 当前节点寻找左边第一个比自己矮的位置，和右边第一个比自己矮的位置
            // 遍历过的元素都在栈里
            // 栈：如果递增的话，那么就是求右边第一个比自己大的元素
            // 栈：如果递减的话，那么就是求右边第一个比自己小的元素

             // 以每一根柱子为基准，得出最大矩形面积
            for(int i = 1; i < heights.length; i++){
                // 注意heights[i]和heights[stack.peek()]比较，stack.peek()是下标
                if (heights[i] > heights[stack.peek()]){
                    stack.push(i);
                }else if (heights[i] == heights[stack.peek()]){
                    stack.pop(); // 这个可以加，可以不加，效果一样，思路不同
                    stack.push(i);
                }else{
                    while(heights[i] < heights[stack.peek()]){ // 注意是while
                        int mid = stack.peek();
                        stack.pop();
                        int left = stack.peek();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = Math.max(result, w * h);
                    }
                    stack.push(i);
                }
            }
            return result;
        }

        public static void main(String[] args) {
            int[] heights = new int[]{2,1,5,6,2,3};
            new LargestRectangleArea().largestRectangleArea(heights);
        }
    }
}
